% !TEX root = TMV_Documentation.tex

\section{Permutations}
\index{Permutation}
\label{Permutation}

The \tt{Permutation} class is our permutation matrix class.
A permutation matrix is square matrix with exactly one 1 in each row and
column, and all the rest of the elements equal to zero.

However, internally we do not store a permutation this way.
Instead, we treat a permutation as a series of pair-wise interchanges.
This seems to be the fastest way to apply a permutation to a matrix or
vector, rather than using an index-based method.

Also, I didn't bother to have a PermutationView class.  Instead, the 
Permutation object keeps track of whether it owns its data or is just
referencing values kept somewhere else.  Whenever you perform 
a mutable action on the object, it copies the values if necessary.
So you cannot indirectly modify another Permutation the way you can
with MatrixView.

\subsection{Constructors}
\index{Permutation!Constructors}
\label{Permutation_Constructors}

\begin{itemize}
\item 
\begin{tmvcode}
tmv::Permutation p(size_t n)
\end{tmvcode}
Makes an \tt{n} $\times$ \tt{n} \tt{Permutation} set initially to the identity matrix.

\item
\begin{tmvcode}
tmv::Permutation p(size_t n, const int* pp, bool isinv, int det)
\end{tmvcode}
Makes an \tt{n} $\times$ \tt{n} \tt{Permutation} using the provided values as the 
list of interchanges.  The meaning of pp is that \tt{v=p*v} is equivalent to
\begin{tmvcode}
if (isinv) v.reversePermute(pp);
else v.permute(pp);
\end{tmvcode}
The last two parameters may be omitted.  If \tt{det} is omitted, it will be calculated
from the input values.  And if \tt{isinv} is omitted, it is taken to be \tt{false}.

\end{itemize}


\subsection{Access}
\index{Permutation!Access methods}
\label{Permutation_Access}

\begin{tmvcode}
p.resize(size_t new_size)
\end{tmvcode}
\index{Permutation!Methods!resize}

\begin{tmvcode}
p.nrows() = p.ncols() = p.colsize() = p.rowsize() = p.size()
p(i,j)
\end{tmvcode}
\index{Permutation!Methods!nrows}
\index{Permutation!Methods!ncols}
\index{Permutation!Methods!rowsize}
\index{Permutation!Methods!colsize}
\index{Permutation!Methods!size}
\index{Permutation!Methods!operator()}
Note: Because of the way the permutation is stored, \tt{p(i,j)} is not
terribly efficient.  It takes $O(N)$ time to calculate.  Also, there is no
mutable version like there is for most matrices.

\begin{tmvcode}
p.transpose() = p.inverse()
\end{tmvcode}
\index{Permutation!Methods!transpose}
\index{Permutation!Methods!inverse}
These are the same, and they do not create new storage.  So statements like
\tt{v = p.transpose() * v} are efficient.

\begin{tmvcode}
const int* p.getValues()
\end{tmvcode}
Get the indices of the interchanges.  These are equivalent to the \tt{pp} values
described above for the constructor.

\begin{tmvcode}
bool p.isInverse()
\end{tmvcode}
Returns true the the interchange values are taken in the reverse order (last to first)
or false if not.
\vspace{12pt}

\subsection{Functions}
\index{Permutation!Functions of}
\label{Permutation_Functions}

Most of these functions aren't very interesting, since most of them have 
trivial values like 1 or n.  But we provide them all for consistency with the 
functions that other matrices provide.

\begin{tmvcode}
int p.norm1() = Norm1(p) = 1
int p.norm2() = Norm2(p) = p.doNorm2() = 1
int p.normInf() = NormInf(p) = 1
int p.maxAbsElement() = MaxAbsElement(p) = 1
int p.maxAbs2Element() = MaxAbs2Element(p) = 1
double p.normF() = NormF(p) = p.norm() = Norm(p) = sqrt(n)
int p.normSq() = NormSq(p) = n
double p.normSq(double scale) = n*scale^2
int p.trace() = Trace(p)
int p.sumElements() = SumElements(p) = n
int p.sumAbsElements() = SumAbsElements(p) = n
int p.sumAbs2Elements() = SumAbs2Elements(p) = n
int p.det() = Det(p)
int p.logDet(int* sign=0) = LogDet(p)
bool p.isSingular() = false
int p.condition() = 1
int p.doCondition() = 1
pinv = p.inverse() = Inverse(p)
p.makeInverse(Matrix<T>& minv)
p.makeInverseATA(Matrix<T>& cov)
\end{tmvcode}
\index{Permutation!Functions of!Norm1}
\index{Permutation!Functions of!Norm2}
\index{Permutation!Functions of!NormInf}
\index{Permutation!Functions of!MaxAbsElement}
\index{Permutation!Functions of!MaxAbs2Element}
\index{Permutation!Methods!norm1}
\index{Permutation!Methods!norm2}
\index{Permutation!Methods!doNorm2}
\index{Permutation!Methods!normInf}
\index{Permutation!Methods!maxAbsElement}
\index{Permutation!Methods!maxAbs2Element}
\index{Permutation!Functions of!Norm}
\index{Permutation!Functions of!NormF}
\index{Permutation!Functions of!NormSq}
\index{Permutation!Functions of!Trace}
\index{Permutation!Functions of!SumElements}
\index{Permutation!Functions of!SumAbsElements}
\index{Permutation!Functions of!SumAbs2Elements}
\index{Permutation!Functions of!Det}
\index{Permutation!Functions of!LogDet}
\index{Permutation!Functions of!Inverse}
\index{Permutation!Methods!norm}
\index{Permutation!Methods!normF}
\index{Permutation!Methods!normSq}
\index{Permutation!Methods!trace}
\index{Permutation!Methods!sumElements}
\index{Permutation!Methods!sumAbsElements}
\index{Permutation!Methods!sumAbs2Elements}
\index{Permutation!Methods!det}
\index{Permutation!Methods!logDet}
\index{Permutation!Methods!isSingular}
\index{Permutation!Methods!condition}
\index{Permutation!Methods!doCondition}
\index{Permutation!Methods!inverse}
\index{Permutation!Methods!makeInverse}
\index{Permutation!Methods!makeInverseATA}

\begin{tmvcode}
p.setToIdentity()
p.transposeSelf()
p.invertSelf()
Swap(p1,p2)
\end{tmvcode}
\index{Permutation!Methods!setToIdentity}
\index{Permutation!Methods!transposeSelf}
\index{Permutation!Methods!invertSelf}
\index{Permutation!Functions of!Swap}

\subsection{Arithmetic}
\index{Permutation!Arithmetic}
\label{Permutation_Arithmetic}

\begin{tmvcode}
v2 = p * v1
v2 = v1 * p
v2 = v1 / p
v2 = v1 % p
v *= p
v /= p
v %= p
m2 = p * m1
m2 = m1 * p
m2 = m1 / p
m2 = m1 % p
m *= p
m /= p
m %= p
p1 == p2
p1 != p2
\end{tmvcode}

\subsection{Input/Output}
\index{Permutation!Input/output}
\label{Permutation_IO}

The simplest output is the usual:
\begin{tmvcode}
os << p
\end{tmvcode}
where \tt{os} is any \tt{std::ostream}.
The output format is the same as for a \tt{Matrix}, including all the 0's.
(See \ref{Matrix_IO}.)

There is also a compact format:
\begin{tmvcode}
p.writeCompact(os)
\end{tmvcode}
\index{Permutation!Methods!writeCompact}
which outputs in the format:
\begin{tmvcode}
P n isinv ( pp[0]  pp[1]  ...  pp[n-1] )
\end{tmvcode}
where \tt{isinv} is a boolean (1 or 0), and the \tt{pp} values are the 
indices of the interchanges.
In other words, the permutation could be created as
\begin{tmvcode}
Permutation p(n,pp,isinv);
\end{tmvcode}

The same (compact, that is) format can be read back in the usual two ways:
\begin{tmvcode}
tmv::Permutation p(n);
is >> p;
std::auto_ptr<tmv::Permutation> pptr;
is >> pptr;
\end{tmvcode}
where the first gives an error if \tt{p} is the wrong size and the second allocates
a new \tt{Permutation} that is the correct size.
\index{Permutation!Methods!write}
\index{Permutation!Methods!writeCompact}
\index{Permutation!Methods!read}


